module Diccionario (Diccionario, vacio, definir, definirVarias, obtener, claves, arbolDeDicc, maybeObtener) where  


import Maybe
import List
import Arbol23


------------------------------------------------------------------------
---- Definición de tipos. ----
------------------------------------------------------------------------

type Comp clave = clave -> clave -> Bool
type Estr clave valor = Arbol23 (clave, valor) clave

---- El comparador es por menor. ----
data Diccionario clave valor = 
    Dicc {cmp :: Comp clave, estructura :: Maybe (Estr clave valor)}


------------------------------------------------------------------------
---- Funciones provistas por la cátedra. ----
------------------------------------------------------------------------

---- Insertar. ----
------------------------------------------------------------------------
---- Inserta un nuevo par (clave, valor) en una estructura  ---- 
---- que ya tiene al menos un dato.                         ---- 

insertar :: clave -> valor -> Comp clave -> Estr clave valor -> Estr clave valor
insertar c v comp a23 = interceptar (insertarYPropagar c v comp a23) 
                        id (\s1 (c1, s2) -> Dos c1 s1 s2)


------------------------------------------------------------------------

---- Interceptar. ----
------------------------------------------------------------------------
---- Maneja el caso en el que la segunda componente es Nothing. ----
interceptar :: (a, Maybe b) -> (a -> c) -> (a -> b -> c) -> c
interceptar (x,y) f1 f2 = case y of
                            Nothing -> f1 x
                            Just z  -> f2 x z


------------------------------------------------------------------------

---- Insertar Y Propagar. ----
------------------------------------------------------------------------
---- Inserta una clave con su valor correspondiente.    ----
---- Si se actualiza el índice, el cambio se propaga    ----
---- hacia arriba para mantener balanceado el árbol.    ----
---- Usamos recursión explícita porque este tipo de     ----
---- recursión no es estructural (porque no se          ----
---- aplica a todos los hijos).                         ----

insertarYPropagar :: clave -> valor -> Comp clave -> Estr clave valor
            -> (Estr clave valor, Maybe (clave, Estr clave valor))
insertarYPropagar c v comp a23 = let rec = insertarYPropagar c v comp in case a23 of
	---- Si es hoja, elegimos la máxima de las claves y ----
    ---- propagamos el balanceo hacia arriba.           ----
	Hoja (ch,vh) -> if comp c ch 
				then (Hoja (c,v), Just (ch, Hoja (ch,vh)))
				else (Hoja (ch, vh), Just (c, Hoja (c,v)))
	
    ---- Si el actual es Nodo-Dos, o se queda en forma Nodo-Dos     ----
    ---- o se transforma en Nodo-Tres; no puede ocurrir que haya    ----
    ---- propagación hacia arriba (retornamos Nothing).             ----
	Dos c1 a1 a2 -> (if comp c c1
				then 
				---- La clave c va del lado izquierdo.  ----
					interceptar (rec a1) 
						(\s1 -> Dos c1 s1 a2)
						(\s1 (c3, s2) -> Tres c3 c1 s1 s2 a2)
				else 
				---- La clave c va del lado derecho.    ----
					interceptar (rec a2) 
						(\s1 -> Dos c1 a1 s1)
						(\s1 (c3, s2) -> Tres c1 c3 a1 s1 s2), Nothing)
	
    ---- Nodo-tres sólo propaga si los de abajo propagan,   ----
    ---- los tres casos son muy similares, sólo cambia en   ----
    ---- que árbol se inserta.                              ----
	Tres c1 c2 a1 a2 a3 -> if comp c c1
				then 
					---- La clave debe ir en el primer árbol.       ---- 
					interceptar (rec a1) 
						(\s1 -> (Tres c1 c2 s1 a2 a3, Nothing))
						(\s1 (c3, s2) -> (Dos c3 s1 s2, Just(c1, Dos c2 a2 a3)))
				else if comp c c2
				then 
					---- La clave debe ir en el árbol del medio.    ----
					interceptar (rec a2) 
						(\s1 -> (Tres c1 c2 a1 s1 a3, Nothing))
						(\s1 (c3, s2) -> (Dos c1 a1 s1, Just(c3, Dos c2 s2 a3)))
				else 
					---- La clave debe ir en el último árbol.       ----
					interceptar (rec a3) 
						(\s1 -> (Tres c1 c2 a1 a2 s1, Nothing))
						(\s1 (c3, s2) -> (Dos c1 a1 a2, Just(c2, Dos c3 s1 s2)))


------------------------------------------------------------------------

---- Definir Varias. ----
------------------------------------------------------------------------
---- Supone que la lista no tiene claves repetidas. ----

definirVarias :: [(clave, valor)] -> Diccionario clave valor 
                    -> Diccionario clave valor
definirVarias = (flip.foldr.uncurry) definir



------------------------------------------------------------------------
---- Funciones pedidas. ----
------------------------------------------------------------------------

---- Función genérica para usar sobre Maybe a, que separa    ---- 
---- los casos en los que es Nothing de los que no.          ----

maybeEstr :: a -> (b -> a) -> Maybe b -> a
maybeEstr casoNothing casoJust e = case e of 
    Nothing -> casoNothing
    Just a -> casoJust a


---- vacio. ----
------------------------------------------------------------------------
---- Crea un diccionario vacio con la función   ---- 
---- de comparación pasada como parámetro.      ----

vacio :: Comp clave -> Diccionario clave valor
vacio clave = Dicc clave Nothing


------------------------------------------------------------------------

---- Definir. ----
------------------------------------------------------------------------
---- Dada una clave, un valor y un diccionario, define una  ----
---- clave con su valor correspondiente en el diccionario.  ----

definir :: clave -> valor -> Diccionario clave valor -> Diccionario clave valor
definir clave valor (Dicc cmp tree) = Dicc cmp arbol
    where arbol = maybeEstr (Just (Hoja (clave, valor))) 
                (\t -> Just (insertar clave valor cmp t)) tree
        								

------------------------------------------------------------------------

---- Obtener. ----
------------------------------------------------------------------------
---- Dada una clave y un diccionario, devuelve su valor ----
---- si está en el diccionario, y Nothing si no está.   ----

---- Se recorre hasta la hoja correspondiente utilizando las    ----
---- reglas del invariante del arbol 2-3. Se supone que se      ----
---- tiene un arbol 2-3 bien balanceado.                        ----
---- Entonces la complejidad será de O(log n)                   ----

obtener :: Eq clave => clave -> Diccionario clave valor -> Maybe valor
obtener clave (Dicc cmp t) = maybeEstr Nothing
        (\tree -> if esHoja tree then checkClave clave tree
               else obtener clave (elegirDicc clave cmp tree)) t


---- Check Clave. ----
------------------------------------------------------------------------
---- Si la clave de la hoja se corresponde con la buscada,  ----
---- devuelve el valor, y si no devuelve nothing.           ----

checkClave clave (Hoja (ch, vh)) = if clave == ch then Just vh else Nothing


---- Elegir Diccionario. ----
------------------------------------------------------------------------
---- Construye un nuevo diccionario a partir de una clave, una  ----
---- función de comparación y un árbol.                         ----
---- Lo que hace es buscar el árbol al cual la clave debería    ----
---- pertenecer, y construir un diccionario usando ese árbol.   ----

elegirDicc :: clave -> Comp clave -> Arbol23 (clave, valor) clave -> 
            Diccionario clave valor
elegirDicc clave cmp arbol = construirDicc cmp (elegirArbol clave cmp arbol)


---- Elegir Árbol. ----
------------------------------------------------------------------------
---- Dada una clave, una función de comparación y un árbol,     ----
---- elige el árbol al cual la clave debería pertenecer.        ----

elegirArbol :: clave -> Comp clave -> Arbol23 (clave, valor) clave 
            -> Arbol23 (clave, valor) clave
elegirArbol clave cmp = foldA23 (\x -> Hoja x)
    (\x izq der -> if clave `cmp` x then izq else der)
    (\x y izq mid der -> if clave `cmp` x then izq
                            else (if clave `cmp` y then mid else der))

---- Construir Diccionario. ----
------------------------------------------------------------------------
---- Dada una función de comparación y un árbol,    ---- 
---- construye un diccionario.                      ----

construirDicc :: Comp clave -> Arbol23 (clave, valor) clave -> Diccionario clave valor
construirDicc cmp arbol = Dicc cmp (Just arbol)


------------------------------------------------------------------------

---- Claves. ----
------------------------------------------------------------------------
---- Devuelve una lista con todas las claves del diccionario. ----
   
claves :: Diccionario clave valor -> [clave]
claves (Dicc _ tree) = maybeEstr [] clavesArbol tree


---- Claves del árbol. ----
------------------------------------------------------------------------
---- Sólo las hojas tienen claves. Los nodos internos nada más  ----
---- sirven para encontrar la clave en el árbol                 ----
---- (y eventualmente obtener el valor correspondiente).        ----

clavesArbol :: Arbol23 (clave, valor) clave -> [clave]
clavesArbol = fstList . hojas
            
---- Dada una lista de tuplas, devuelve una lista con   ----
---- todas las primeras componentes.                    ----
fstList :: [(a, b)] -> [a]
fstList = foldr (\x rec -> (fst x):rec) []


------------------------------------------------------------------------

---- Maybe Obtener. ----
------------------------------------------------------------------------
---- Como obtener pero recibe maybe clave, y además tiene       ----
---- los parámetros al revés para poder usarla en               ----
---- busquedaDelTesoro de forma currificada (fijando el         ----
---- diccionario). Se usa maybe clave para poder usar lo que    ----
---- devuelve como una nueva clave.                             ----
maybeObtener :: Eq clave => Diccionario clave valor -> Maybe clave -> Maybe valor
maybeObtener dicc = maybeEstr Nothing (\c -> obtener c dicc)


------------------------------------------------------------------------

---- Arbol de un diccionario. ----
------------------------------------------------------------------------
---- Se usa para testear y poder ver el arbol correspondiente   ----
---- a un determinado diccionario.                              ----
---- Require que el arbol exista.                               ----
arbolDeDicc :: Diccionario clave valor -> Arbol23 (clave, valor) clave
arbolDeDicc (Dicc _ tree) = case tree of Just tree -> tree
